#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int> &nums, int target) {
        vector<pair<int, int>> pairs;
        pairs.reserve(nums.size());
        for (int i = 0; i < nums.size(); ++i) {
            pairs.emplace_back(i, nums[i]);
        }

        auto cmp = [](const pair<int, int> &first, const pair<int, int> &second) {
            return first.second < second.second;
        };

        std::sort(pairs.begin(), pairs.end(), cmp);

        int a, b;
        int x, y;

        a = 0;
        b = nums.size() - 1;

        while (a < b) {
            x = pairs[a].second;
            y = pairs[b].second;
            if (x + y == target) {
                break;
            } else if (x + y < target) {
                a++;
            } else {
                b--;
            }
        }

        return {pairs[a].first, pairs[b].first};
    }
};
